from __future__ import division
import struct
import warnings
import os
import random

SURPRESS_WARNINGS = False

NAV_MAGIC_NUMBER  = 0xfeedface

class NAVInvalidFileError(Exception): pass

class NAVWarning(Warning): pass

class NAVTODOWarning(Warning): pass

def warn(info):
    if not SURPRESS_WARNINGS:
        warnings.warn(str(info), NAVWarning)
            
_todo_warned = []
def todo(method):
    if not method in _todo_warned:
        warnings.warn('TODO: %s' % method)
        _todo_warned.append(method)
    
def getBSPFilename(filename):
    return filename[:-3] + 'bsp'

def checkFilesize(checksize, filename):
    return checksize == os.stat(filename).st_size 

class HIDING_SPOT_FLAGS:
    """
    enum 
    { 
        IN_COVER            = 0x01,                            ///< in a corner with good hard cover nearby
        GOOD_SNIPER_SPOT    = 0x02,                            ///< had at least one decent sniping corridor
        IDEAL_SNIPER_SPOT    = 0x04,                            ///< can see either very far, or a large area, or both
        EXPOSED                = 0x08                            ///< spot in the open, usually on a ledge or cliff
    };
    """
    IN_COVER            = 1
    GOOD_SNIPER_SPOT    = 2
    IDEAL_SNIPER_SPOT   = 4
    EXPOSED             = 8
HIDING_SPOT = HIDING_SPOT_FLAGS()

"""
enum NavTraverseType
{
    // NOTE: First 4 directions MUST match NavDirType
    GO_NORTH = 0,
    GO_EAST,
    GO_SOUTH,
    GO_WEST,
    GO_LADDER_UP,
    GO_LADDER_DOWN,
    GO_JUMP,

    NUM_TRAVERSE_TYPES
};
"""
NavTraverseType = ['GO_NORTH', 'GO_EAST', 'GO_SOUTH', 'GO_WEST', 'GO_LADDER_UP',
                   'GO_LADDER_DOWN', 'GO_JUMP']
"""
enum NavDirType
{
    NORTH = 0,
    EAST = 1,
    SOUTH = 2,
    WEST = 3,

    NUM_DIRECTIONS
};
"""
NavDirType = ['NORTH', 'EAST', 'SOUTH', 'WEST']
"""
enum NavAttributeType
{
    NAV_MESH_CROUCH            = 0x0001,                ///< must crouch to use this node/area
    NAV_MESH_JUMP            = 0x0002,                ///< must jump to traverse this area
    NAV_MESH_PRECISE        = 0x0004,                ///< do not adjust for obstacles, just move along area
    NAV_MESH_NO_JUMP        = 0x0008,                ///< inhibit discontinuity jumping
    NAV_MESH_STOP            = 0x0010,                ///< must stop when entering this area
    NAV_MESH_RUN            = 0x0020,                ///< must run to traverse this area
    NAV_MESH_WALK            = 0x0040,                ///< must walk to traverse this area
    NAV_MESH_AVOID            = 0x0080,                ///< avoid this area unless alternatives are too dangerous
    NAV_MESH_TRANSIENT        = 0x0100,                ///< area may become blocked, and should be periodically checked
    NAV_MESH_DONT_HIDE        = 0x0200,                ///< area should not be considered for hiding spot generation
    NAV_MESH_STAND            = 0x0400,                ///< bots hiding in this area should stand
    NAV_MESH_NO_HOSTAGES    = 0x0800,                ///< hostages shouldn't use this area
};
"""
NavAttributeType = {
    'NAV_MESH_CROUCH':      1,
    'NAV_MESH_JUMP':        2,
    'NAV_MESH_PRECISE':     4,
    'NAV_MESH_NO_JUMP':     8,
    'NAV_MESH_STOP':        16,
    'NAV_MESH_RUN':         32,
    'NAV_MESH_WALK':        64,
    'NAV_MESH_AVOID':       128,
    'NAV_MESH_TRANSIENT':   256,
    'NAV_MESH_DONT_HIDE':   512,
    'NAV_MESH_STAND':       1024,
    'NAV_MESH_NO_HOSTAGES': 2048,
}


class Extent(object):
    def __init__(self, xlo=float(), ylo=float(), zlo=float(),
                       xhi=float(), yhi=float(), zhi=float()):
        if type(xlo) in (tuple, list):
            data = xlo
            if len(data) >= 1:
                xlo = data[0]
            if len(data) >= 2:
                ylo = data[1]
            if len(data) >= 3:
                zlo = data[2]
            if len(data) >= 4:
                xhi = data[3]
            if len(data) >= 5:
                yhi = data[4]
            if len(data) == 6:
                zhi = data[5]
        self.hi = Vector(xhi, yhi, zhi)
        self.lo = Vector(xlo, ylo, zlo)
        
    def __str__(self):
        return str({'hi':str(self.hi), 'lo':str(self.lo)})
    __repr__ = __str__
        
    def __getitem__(self, item):
        return self.__dict__[item]
        
        
class Vector(object):
    def __init__(self, x=float(), y=float(), z=float()):
        if type(x) in (tuple, list):
            if len(x) >= 1:
                self.x = x[0]
            if len(x) >= 2:
                self.y = x[1]
            if len(x) == 3:
                self.z = x[2]
        else:
            self.x = x
            self.y = y
            self.z = z
        
    def __getitem__(self, item):
        return self.__dict__[item]
    
    def __add__(self, other):
        if not isinstance(other, Vector):
            other = Vector(instance)
        return Vector(self.x + other.x, self.y + other.y, self.z + other.z)
    
    def __str__(self):
        return str({'x': self.x, 'y': self.y, 'z': self.z})
    __repr__ = __str__
    
    
class Reader:
    def __init__(self, fileobj):
        self.__format_cache = {}
        self.f = fileobj

    def read(self, format='', offset=None):
        if offset:
            self.f.seek(offset)
        if format:
            result = struct.unpack(format, self.f.read(self.getsize(format)))
            if len(result) == 1:
                return result[0]
            return result
    
    def getsize(self, format):
        if format in self.__format_cache:
            return self.__format_cache[format]
        size = struct.Struct(format).size
        self.__format_cache[format] = size
        return size
            
        
class NavHidingSpot:
    def __init__(self, nav):
        """
    HidingSpot::HidingSpot( void )
    {
        m_pos = Vector( 0, 0, 0 );
        m_id = m_nextID++;
        m_flags = 0;
        m_area = NULL;
    
        TheHidingSpotList.AddToTail( this );
    }
        """
        self.pos = Vector()
        self.id = nav.nextID + 1
        self.flags = 0
        self.area = None
        self.nav = nav
        self.read = self.nav.read
        
    def load(self, f, version):
        """
{
    filesystem->Read( &m_id, sizeof(unsigned int), file );
    filesystem->Read( &m_pos, 3 * sizeof(float), file );
    filesystem->Read( &m_flags, sizeof(unsigned char), file );

    // update next ID to avoid ID collisions by later spots
    if (m_id >= m_nextID)
        m_nextID = m_id+1;
}
        """
        self.id = self.read('I')
        self.pos = Vector(self.read('fff'))
        self.flags = self.read('B')
        if self.id >= self.nav.nextID:
            self.nav.nextID = self.id + 1
            
    def PostLoad(self):
        """

        // set our area
        m_area = TheNavMesh->GetNavArea( m_pos + Vector( 0, 0, HalfHumanHeight ) );
    
        AssertMsg( m_area, UTIL_VarArgs("A Hiding Spot is off of the Nav Mesh at (%.0f %.0f %.0f)", m_pos.x, m_pos.y, m_pos.z) );
    
        return NAV_OK;
        """
        self.area = self.nav.getArea(self.pos + Vector(0, 0, 28))
    
    def setPosition(self, pos):
        self.pos = pos
    
    def setFlags(self, flag):
        self.flags |= flag
        
    def __str__(self):
        return str({'pos': self.pos, 'id': self.id, 'flags': self.flags, 'area': self.area})
    
    def __repr__(self):
        return '<navlib.NavHidingSpot: %s>' % self.id

class NavArea:    
    def __init__(self, nav):
        self.nav = nav
        self.read = self.nav.read
        """
void CNavArea::Load( FileHandle_t file, unsigned int version )
{
    // load ID
    filesystem->Read( &m_id, sizeof(unsigned int), file );
        """
        self.id = self.read('I')
        """
    // update nextID to avoid collisions
    if (m_id >= m_nextID)
        m_nextID = m_id+1;
        """
        if self.id > self.nav.nextID:
            self.nav.nextID = self.id + 1
        """
    // load attribute flags
    if ( version <= 8 )
    {
        unsigned char flags = 0;
        filesystem->Read( &flags, sizeof(unsigned char), file );
        m_attributeFlags = flags;
    }
    else
    {
        filesystem->Read( &m_attributeFlags, sizeof(unsigned short), file );
    }
        """
        if self.nav.version <= 8:
            self.flags = self.read('B')
        else:
            self.flags = self.read('H')
        """
    // load extent of area
    filesystem->Read( &m_extent, 6*sizeof(float), file );

    m_center.x = (m_extent.lo.x + m_extent.hi.x)/2.0f;
    m_center.y = (m_extent.lo.y + m_extent.hi.y)/2.0f;
    m_center.z = (m_extent.lo.z + m_extent.hi.z)/2.0f;
        """
        self.extent = Extent(self.read('ffffff'))
        self.center = Vector()
        self.center.x = (self.extent.lo.x + self.extent.hi.x) / 2.0
        self.center.y = (self.extent.lo.y + self.extent.hi.y) / 2.0
        self.center.z = (self.extent.lo.z + self.extent.hi.z) / 2.0
        """
    // load heights of implicit corners
    filesystem->Read( &m_neZ, sizeof(float), file );
    filesystem->Read( &m_swZ, sizeof(float), file );
        """
        self.neZ = self.read('f')
        self.swZ = self.read('f')
        """
void CNavArea::CheckWaterLevel( void )
{
    Vector pos( GetCenter() );
    if ( !TheNavMesh->GetGroundHeight( pos, &pos.z ) )
    {
        m_isUnderwater = false;
        return;
    }

    pos.z += 1;
    m_isUnderwater = (enginetrace->GetPointContents( pos ) & MASK_WATER) != 0;
}
        """
        self.isUnderwater = False
        todo('CNavArea::CheckWaterLevel(); in NavArea.__init__')
        """
    // load connections (IDs) to adjacent areas
    // in the enum order NORTH, EAST, SOUTH, WEST
enum NavDirType
{
    NORTH = 0,
    EAST = 1,
    SOUTH = 2,
    WEST = 3,

    NUM_DIRECTIONS
};
    for( int d=0; d<NUM_DIRECTIONS; d++ )
    {
        // load number of connections for this direction
        unsigned int count;
        int result = filesystem->Read( &count, sizeof(unsigned int), file );
        Assert( result == sizeof(unsigned int) );

        for( unsigned int i=0; i<count; ++i )
        {
            NavConnect connect;
            result = filesystem->Read( &connect.id, sizeof(unsigned int), file );
            Assert( result == sizeof(unsigned int) );

            // don't allow self-referential connections
            if ( connect.id != m_id )
            {
                m_connect[d].AddToTail( connect );
            }
        }
    }
        """
        self.connections = []
        for x in range(4):
            count = self.read('I')
            for y in range(count):
                cid = self.read('I')
                if cid != self.id:
                    self.connections.append(cid)
        """
    //
    // Load hiding spots
    //

    // load number of hiding spots
    unsigned char hidingSpotCount;
    filesystem->Read( &hidingSpotCount, sizeof(unsigned char), file );
        """
        self.hidingSpotCount = self.read('B')
        """

    if (version == 1)
    {
        // load simple vector array
        Vector pos;
        for( int h=0; h<hidingSpotCount; ++h )
        {
            filesystem->Read( &pos, 3 * sizeof(float), file );

            // create new hiding spot and put on master list
            HidingSpot *spot = TheNavMesh->CreateHidingSpot();
            spot->SetPosition( pos );
            spot->SetFlags( HidingSpot::IN_COVER );
            m_hidingSpotList.AddToTail( spot );
        }
    }
    else
    {
        // load HidingSpot objects for this area
        for( int h=0; h<hidingSpotCount; ++h )
        {
            // create new hiding spot and put on master list
            HidingSpot *spot = TheNavMesh->CreateHidingSpot();

            spot->Load( file, version );
            
            m_hidingSpotList.AddToTail( spot );
        }
    }
HidingSpot::HidingSpot( void )
{
    m_pos = Vector( 0, 0, 0 );
    m_id = m_nextID++;
    m_flags = 0;
    m_area = NULL;

    TheHidingSpotList.AddToTail( this );
}
        """
        self.hidingspots = []
        for x in range(self.hidingSpotCount):
            spot = NavHidingSpot(self.nav)
            if self.nav.version == 1:
                pos = Vector(self.read('fff'))
                spot.setPosition(pos)
                spot.setFlags(HIDING_SPOT.IN_COVER)
            else:
                spot.load(self.nav.f, self.nav.version)
            self.hidingspots.append(spot)
            self.nav.hidingSpots.append(spot)
        """
    //
    // Load number of approach areas
    //
    filesystem->Read( &m_approachCount, sizeof(unsigned char), file );
        """
        self.approachCount = self.read('B')
        """
    struct ApproachInfo
    {
        NavConnect here;                                        ///< the approach area
        NavConnect prev;                                        ///< the area just before the approach area on the path
        NavTraverseType prevToHereHow;
        NavConnect next;                                        ///< the area just after the approach area on the path
        NavTraverseType hereToNextHow;
    };
    union NavConnect
    {
        unsigned int id;
        CNavArea *area;
    
        bool operator==( const NavConnect &other ) const
        {
            return (area == other.area) ? true : false;
        }
    };
    // load approach area info (IDs)
    unsigned char type;
    for( int a=0; a<m_approachCount; ++a )
    {
        filesystem->Read( &m_approach[a].here.id, sizeof(unsigned int), file );

        filesystem->Read( &m_approach[a].prev.id, sizeof(unsigned int), file );
        filesystem->Read( &type, sizeof(unsigned char), file );
        m_approach[a].prevToHereHow = (NavTraverseType)type;

        filesystem->Read( &m_approach[a].next.id, sizeof(unsigned int), file );
        filesystem->Read( &type, sizeof(unsigned char), file );
        m_approach[a].hereToNextHow = (NavTraverseType)type;
    }
        """
        self.approach = []
        for x in range(self.approachCount):
            approach = {}
            approach['here'] = self.read('I')
            approach['prev'] = self.read('I')
            typ = self.read('B')
            if typ >= len(NavTraverseType):
                warn('approach type out of range: %s' % typ)
            else:
                approach['prevToHereHow'] = NavTraverseType[typ]
            approach['next'] = self.read('I')
            typ = self.read('B')
            if typ >= len(NavTraverseType):
                warn('approach type out of range: %s' % typ)
            else:
                approach['hereToNextHow'] = NavTraverseType[typ]
            self.approach.append(approach)
        """

    //
    // Load encounter paths for this area
    //
    unsigned int count;
    filesystem->Read( &count, sizeof(unsigned int), file );
        """
        count = self.read('I')
        """
struct SpotEncounter
{
    NavConnect from;
    NavDirType fromDir;
    NavConnect to;
    NavDirType toDir;
    Ray path;                                    ///< the path segment
    SpotOrderList spotList;                        ///< list of spots to look at, in order of occurrence
};
    if (version < 3)
    {
        // old data, read and discard
        for( unsigned int e=0; e<count; ++e )
        {
            SpotEncounter encounter;

            filesystem->Read( &encounter.from.id, sizeof(unsigned int), file );
            filesystem->Read( &encounter.to.id, sizeof(unsigned int), file );

            filesystem->Read( &encounter.path.from.x, 3 * sizeof(float), file );
            filesystem->Read( &encounter.path.to.x, 3 * sizeof(float), file );

            // read list of spots along this path
            unsigned char spotCount;
            filesystem->Read( &spotCount, sizeof(unsigned char), file );
        
            for( int s=0; s<spotCount; ++s )
            {
                Vector pos;
                filesystem->Read( &pos, 3*sizeof(float), file );
                filesystem->Read( &pos, sizeof(float), file );
            }
        }
        return;
    }
        """
        if self.nav.version < 3:
            # OLD DATA, DISCARD
            for x in range(count):
                discard = self.read('IIffffff')
                spotCount = self.read('B')
                for x in range(spotCount):
                    discard = self.read('ffff')
            return
        """
    for( unsigned int e=0; e<count; ++e )
    {
        SpotEncounter *encounter = new SpotEncounter;

        filesystem->Read( &encounter->from.id, sizeof(unsigned int), file );

        unsigned char dir;
        filesystem->Read( &dir, sizeof(unsigned char), file );
        encounter->fromDir = static_cast<NavDirType>( dir );

        filesystem->Read( &encounter->to.id, sizeof(unsigned int), file );

        filesystem->Read( &dir, sizeof(unsigned char), file );
        encounter->toDir = static_cast<NavDirType>( dir );

        // read list of spots along this path
        unsigned char spotCount;
        filesystem->Read( &spotCount, sizeof(unsigned char), file );
    
        SpotOrder order;
        for( int s=0; s<spotCount; ++s )
        {
            filesystem->Read( &order.id, sizeof(unsigned int), file );

            unsigned char t;
            filesystem->Read( &t, sizeof(unsigned char), file );

            order.t = (float)t/255.0f;

            encounter->spotList.AddToTail( order );
        }

        m_spotEncounterList.AddToTail( encounter );
    }
        """
        for x in range(count):
            encounter = {}
            encounter['from'] = self.read('I')
            encounter['fromDir'] = NavDirType[self.read('B')]
            encounter['to'] = self.read('I')
            encounter['toDir'] = NavDirType[self.read('B')]
            encounter['spotList'] = []
            spotCount = self.read('B')
            for x in xrange(spotCount):
                order = {}
                order['id'] = self.read('I')
                order['t'] = float(self.read('B')) / 255.0
                encounter['spotList'].append(order)
            self.nav.spotEncounterList.append(encounter)
        """
    if (version < 5)
        return;
        """
        if self.nav.version < 5:
            return
        """
    //
    // Load Place data
    //
    PlaceDirectory::IndexType entry;
    filesystem->Read( &entry, sizeof(entry), file );
        """
        entry = self.read('H')
        """
    // convert entry to actual Place
    SetPlace( placeDirectory.IndexToPlace( entry ) );
        """
        todo('SetPlace( placeDirectory.IndexToPlace( entry ) ); in Nav.__init__')
        """
    if ( version < 7 )
        return;
        """
        if self.nav.version < 7:
            return
        """
    // load ladder data
    for ( int dir=0; dir<CNavLadder::NUM_LADDER_DIRECTIONS; ++dir )
    {
        filesystem->Read( &count, sizeof(unsigned int), file );
        {
            for( unsigned int i=0; i<count; ++i )
            {
                NavLadderConnect connect;
                filesystem->Read( &connect.id, sizeof(unsigned int), file );

                bool alreadyConnected = false;
                for ( int j=0; j<m_ladder[dir].Count(); ++j )
                {
                    if ( m_ladder[dir][j].id == connect.id )
                    {
                        alreadyConnected = true;
                        break;
                    }
                }

                if ( !alreadyConnected )
                {
                    m_ladder[dir].AddToTail( connect );
                }
            }
        }
    }
        """
        self.ladder = [[],[]]
        for direction in range(2): # LADDER_UP, LADDER_DOWN
            count = self.read('I')
            for y in range(count):
                connect = {}
                connect['id'] = self.read('I')
                alreadyConnected = False
                for z in range(len(self.ladder[direction])):
                    if self.ladder[direction][z]['id'] == connect['id']:
                        alreadyConnected = True
                        break
                if not alreadyConnected:
                    self.ladder[direction].append(connect)
        """

    if ( version < 8 )
        return;
        """
        if self.nav.version < 8:
            return
        """

    // load earliest occupy times
    for( int i=0; i<MAX_NAV_TEAMS; ++i )
    {
        // no spot in the map should take longer than this to reach
        filesystem->Read( &m_earliestOccupyTime[i], sizeof(m_earliestOccupyTime[i]), file );
    }
}
        """
        self.earliestOccupyTime = []
        for x in range(2): # MAX_NAV_TEAMS = 2 (nav_area.h, 18)
            self.earliestOccupyTime.append(self.read('f'))
            
    def PostLoad(self):
        todo('NavArea.PostLoad')
        """
        NavErrorType error = NAV_OK;
    
        for ( int dir=0; dir<CNavLadder::NUM_LADDER_DIRECTIONS; ++dir )
        {
            FOR_EACH_LL( m_ladder[dir], it )
            {
                NavLadderConnect& connect = m_ladder[dir][it];
    
                unsigned int id = connect.id;
    
                if ( TheNavMesh->GetLadders().Find( connect.ladder ) == TheNavMesh->GetLadders().InvalidIndex() )
                {
                    connect.ladder = TheNavMesh->GetLadderByID( id );
                }
    
                if (id && connect.ladder == NULL)
                {
                    Msg( "CNavArea::PostLoad: Corrupt navigation ladder data. Cannot connect Navigation Areas.\n" );
                    error = NAV_CORRUPT_DATA;
                }
            }
        }
        """
        """
        // connect areas together
        for( int d=0; d<NUM_DIRECTIONS; d++ )
        {
            FOR_EACH_LL( m_connect[d], it )
            {
                NavConnect *connect = &m_connect[ d ][ it ];
    
                unsigned int id = connect->id;
                connect->area = TheNavMesh->GetNavAreaByID( id );
                if (id && connect->area == NULL)
                {
                    Msg( "CNavArea::PostLoad: Corrupt navigation data. Cannot connect Navigation Areas.\n" );
                    error = NAV_CORRUPT_DATA;
                }
            }
        }
        """
        """
        // resolve approach area IDs
        for( int a=0; a<m_approachCount; ++a )
        {
            m_approach[a].here.area = TheNavMesh->GetNavAreaByID( m_approach[a].here.id );
            if (m_approach[a].here.id && m_approach[a].here.area == NULL)
            {
                Msg( "CNavArea::PostLoad: Corrupt navigation data. Missing Approach Area (here).\n" );
                error = NAV_CORRUPT_DATA;
            }
    
            m_approach[a].prev.area = TheNavMesh->GetNavAreaByID( m_approach[a].prev.id );
            if (m_approach[a].prev.id && m_approach[a].prev.area == NULL)
            {
                Msg( "CNavArea::PostLoad: Corrupt navigation data. Missing Approach Area (prev).\n" );
                error = NAV_CORRUPT_DATA;
            }
    
            m_approach[a].next.area = TheNavMesh->GetNavAreaByID( m_approach[a].next.id );
            if (m_approach[a].next.id && m_approach[a].next.area == NULL)
            {
                Msg( "CNavArea::PostLoad: Corrupt navigation data. Missing Approach Area (next).\n" );
                error = NAV_CORRUPT_DATA;
            }
        }
        """
        """
        // resolve spot encounter IDs
        SpotEncounter *e;
        FOR_EACH_LL( m_spotEncounterList, it )
        {
            e = m_spotEncounterList[ it ];
    
            e->from.area = TheNavMesh->GetNavAreaByID( e->from.id );
            if (e->from.area == NULL)
            {
                Msg( "CNavArea::PostLoad: Corrupt navigation data. Missing \"from\" Navigation Area for Encounter Spot.\n" );
                error = NAV_CORRUPT_DATA;
            }
    
            e->to.area = TheNavMesh->GetNavAreaByID( e->to.id );
            if (e->to.area == NULL)
            {
                Msg( "CNavArea::PostLoad: Corrupt navigation data. Missing \"to\" Navigation Area for Encounter Spot.\n" );
                error = NAV_CORRUPT_DATA;
            }
    
            if (e->from.area && e->to.area)
            {
                // compute path
                float halfWidth;
                ComputePortal( e->to.area, e->toDir, &e->path.to, &halfWidth );
                ComputePortal( e->from.area, e->fromDir, &e->path.from, &halfWidth );
    
                const float eyeHeight = HalfHumanHeight;
                e->path.from.z = e->from.area->GetZ( e->path.from ) + eyeHeight;
                e->path.to.z = e->to.area->GetZ( e->path.to ) + eyeHeight;
            }
        
            // resolve HidingSpot IDs
            FOR_EACH_LL( e->spotList, sit )
            {
                SpotOrder *order = &e->spotList[ sit ];
    
                order->spot = GetHidingSpotByID( order->id );
                if (order->spot == NULL)
                {
                    Msg( "CNavArea::PostLoad: Corrupt navigation data. Missing Hiding Spot\n" );
                    error = NAV_CORRUPT_DATA;
                }
            }
        }
        """
        """
        // build overlap list
        /// @todo Optimize this
        FOR_EACH_LL( TheNavAreaList, nit )
        {
            CNavArea *area = TheNavAreaList[ nit ];
    
            if (area == this)
                continue;
    
            if (IsOverlapping( area ))
                m_overlapList.AddToTail( area );
        }
    
        return error;
        """
        
    def ComputeEarliestOccupyTimes(self):
        todo('NavArea.ComputeEarliestOccupyTimes')
        """
    #ifdef CSTRIKE_DLL
        /// @todo Derive cstrike-specific navigation classes
    
        for( int i=0; i<MAX_NAV_TEAMS; ++i )
        {
            // no spot in the map should take longer than this to reach
            m_earliestOccupyTime[i] = 120.0f;
        }
    
        if (nav_quicksave.GetBool())
            return;
    
        // maximum player speed in units/second
        const float playerSpeed = 240.0f;
    
        ShortestPathCost cost;
        CBaseEntity *spot;
    
        // determine the shortest time it will take a Terrorist to reach this area
        int team = TEAM_TERRORIST % MAX_NAV_TEAMS;
        for( spot = gEntList.FindEntityByClassname( NULL, "info_player_terrorist" );
             spot;
             spot = gEntList.FindEntityByClassname( spot, "info_player_terrorist" ) )
        {
            float travelDistance = NavAreaTravelDistance( spot->GetAbsOrigin(), m_center, cost );
            if (travelDistance < 0.0f)
                continue;
    
            float travelTime = travelDistance / playerSpeed;
            if (travelTime < m_earliestOccupyTime[ team ])
            {
                m_earliestOccupyTime[ team ] = travelTime;
            }
        }
    
    
        // determine the shortest time it will take a CT to reach this area
        team = TEAM_CT % MAX_NAV_TEAMS;
        for( spot = gEntList.FindEntityByClassname( NULL, "info_player_counterterrorist" );
             spot;
             spot = gEntList.FindEntityByClassname( spot, "info_player_counterterrorist" ) )
        {
            float travelDistance = NavAreaTravelDistance( spot->GetAbsOrigin(), m_center, cost );
            if (travelDistance < 0.0f)
                continue;
    
            float travelTime = travelDistance / playerSpeed;
            if (travelTime < m_earliestOccupyTime[ team ])
            {
                m_earliestOccupyTime[ team ] = travelTime;
            }
        }
    
    #else
        for( int i=0; i<MAX_NAV_TEAMS; ++i )
        {
            m_earliestOccupyTime[i] = 0.0f;
        }
    #endif
        """
            
    def getDict(self):
        d = {'id': self.id,
             'flags': self.flags,
             'extent': self.extent,
             'center': self.center,
             'neZ': self.neZ,
             'swZ': self.swZ,
             'isUnderwater': 'NOT IMPLEMENTED YET',
            }
        if self.nav.version < 7:
            return str(d)
        d['ladder'] = self.ladder
        if self.nav.version < 8:
            return str(d)
        d['earliestOccupyTime'] = self.earliestOccupyTime
        return d
    
    def __str__(self):
        return str(self.getDict())
    
    def __repr__(self):
        return '<navlib.NavArea: %s>' % self.id
    
    
class NavLadder:
    def __init__(self, nav):
        self.nav = nav
        self.read = nav.read
        self.version = nav.version
        """
void CNavLadder::Load( FileHandle_t file, unsigned int version )
{
    // load ID
    filesystem->Read( &m_id, sizeof(unsigned int), file );
        """
        self.id = self.read('I')
        """
    // update nextID to avoid collisions
    if (m_id >= m_nextID)
        m_nextID = m_id+1;
        """
        if self.id >= self.nav.nextID:
            self.nav.nextID = self.id + 1
        """
    // load extent of ladder
    filesystem->Read( &m_width, sizeof(float), file );
        """
        self.width = self.read('f')
        """
    // load top endpoint of ladder
    filesystem->Read( &m_top, 3*sizeof(float), file );
        """
        self.top = Vector(self.read('fff'))
        """
    // load bottom endpoint of ladder
    filesystem->Read( &m_bottom, 3*sizeof(float), file );
        """
        self.bottom = Vector(self.read('fff'))
        """
    // load ladder length
    filesystem->Read( &m_length, sizeof(float), file );
        """
        self.length = self.read('f')
        """
    // load direction
    filesystem->Read( &m_dir, sizeof(m_dir), file );
    SetDir( m_dir ); // regenerate the surface normal
        """
        self.dir = self.read('I')
        """
    // load dangling status
    if ( version == 6 )
    {
        bool m_isDangling;
        filesystem->Read( &m_isDangling, sizeof(m_isDangling), file );
    }
        """
        if self.version == 6:
            self.isDangling = self.read('?')
        """
    // load IDs of connecting areas
    unsigned int id;
    filesystem->Read( &id, sizeof(id), file );
    m_topForwardArea = TheNavMesh->GetNavAreaByID( id );
        """
        todo('NavLadder.__init__')
        """
    filesystem->Read( &id, sizeof(id), file );
    m_topLeftArea = TheNavMesh->GetNavAreaByID( id );
        """
        """
    filesystem->Read( &id, sizeof(id), file );
    m_topRightArea = TheNavMesh->GetNavAreaByID( id );
        """
        """
    filesystem->Read( &id, sizeof(id), file );
    m_topBehindArea = TheNavMesh->GetNavAreaByID( id );
        """
        """
    filesystem->Read( &id, sizeof(id), file );
    m_bottomArea = TheNavMesh->GetNavAreaByID( id );
    if ( !m_bottomArea )
    {
        DevMsg( "ERROR: Unconnected ladder #%d bottom at ( %g, %g, %g )\n", m_id, m_bottom.x, m_bottom.y, m_bottom.z );
    }
        """
        """
    // can't include behind area, since it is not used when going up a ladder
    if (!m_topForwardArea && !m_topLeftArea && !m_topRightArea)
        DevMsg( "ERROR: Unconnected ladder #%d top at ( %g, %g, %g )\n", m_id, m_top.x, m_top.y, m_top.z );
}
        """


class NAV:
    def __init__(self, filename):
        self.__format_cache = {}
        self.filename = filename
        self.f = open(filename, 'rb')
        self.reader = Reader(self.f)
        self.read = self.reader.read
        self.nextID = 1
        self.gridCellSize = 300.0
        # get magic number and version
        self.magic, self.version = self.read('II')
        # check magic number
        if self.magic != NAV_MAGIC_NUMBER:
            raise NAVInvalidFileError, 'Magic Number is wrong (%s)' % self.magic
        # if version 4 or higher crosscheck bsp filesize
        if self.version >= 4:
            """
            // get size of source bsp file and verify that the bsp hasn't changed
            unsigned int saveBspSize;
            filesystem->Read( &saveBspSize, sizeof(unsigned int), file );
    
            // verify size
            char *bspFilename = GetBspFilename( filename );
            if ( bspFilename == NULL )
            {
                filesystem->Close( file );
                return NAV_INVALID_FILE;
            }
    
            unsigned int bspSize = filesystem->Size( bspFilename );
    
            if (bspSize != saveBspSize && !navIsInBsp)
            {
                if ( engine->IsDedicatedServer() )
                {
                    // Warning doesn't print to the dedicated server console, so we'll use Msg instead
                    Msg( "The Navigation Mesh was built using a different version of this map.\n" );
                }
                else
                {
                    Warning( "The Navigation Mesh was built using a different version of this map.\n" );
                }
                m_isFromCurrentMap = false;
            }
            """
            self.bspsize = self.read('I')
            bspName = getBSPFilename(filename)
            if not bspName:
                raise NAVInvalidFileError, 'no bsp'
            if not checkFilesize(self.bspsize, bspName):
                raise NAVInvalidFileError, 'different bsp'
        # if version 5 or higher, read place names
        if self.version >= 5:
            """
            {
                placeDirectory.Load( file );
            }
            typedef unsigned short IndexType;
            void Load( FileHandle_t file )
            {
                // read number of entries
                IndexType count;
                filesystem->Read( &count, sizeof(IndexType), file );
        
                m_directory.RemoveAll();
        
                // read each entry
                char placeName[256];
                unsigned short len;
                for( int i=0; i<count; ++i )
                {
                    filesystem->Read( &len, sizeof(unsigned short), file );
                    filesystem->Read( placeName, len, file );
        
                    AddPlace( TheNavMesh->NameToPlace( placeName ) );
                }
            }
            """
            count = self.read('H')
            self.places = []
            for x in range(count):
                length = self.read('H')
                placeName = self.read('%ss' % length)
                self.places.append(placeName)
        # get number of areas
        self.areacount = self.read('I')
        self.extent = Extent(9999999999.9, 9999999999.9, 0.0 - 9999999999.9, -9999999999.9)
        
        # load areas and compute total extent
        """
        for( i=0; i<count; ++i )
        {
            CNavArea *area = new CNavArea;
            area->Load( file, version );
            TheNavAreaList.AddToTail( area );
    
            const Extent &areaExtent = area->GetExtent();
    
            // check validity of nav area
            if (areaExtent.lo.x >= areaExtent.hi.x || areaExtent.lo.y >= areaExtent.hi.y)
                Warning( "WARNING: Degenerate Navigation Area #%d at ( %g, %g, %g )\n", 
                            area->GetID(), area->m_center.x, area->m_center.y, area->m_center.z );
    
            if (areaExtent.lo.x < extent.lo.x)
                extent.lo.x = areaExtent.lo.x;
            if (areaExtent.lo.y < extent.lo.y)
                extent.lo.y = areaExtent.lo.y;
            if (areaExtent.hi.x > extent.hi.x)
                extent.hi.x = areaExtent.hi.x;
            if (areaExtent.hi.y > extent.hi.y)
                extent.hi.y = areaExtent.hi.y;
        }
        """
        self.areas = []
        self.hidingSpots = []
        self.nonCrouchAreas = [] # for teleports, speedup of a factor 60!
        self.spotEncounterList = []
        for x in range(self.areacount):
            area = NavArea(self)
            self.areas.append(area)
            if area.extent.lo.x < self.extent.lo.x:
                self.extent.lo.x = area.extent.lo.x
            if area.extent.lo.y < self.extent.lo.y:
                self.extent.lo.y = area.extent.lo.y
            if area.extent.hi.x > self.extent.hi.x:
                self.extent.hi.x = area.extent.hi.x
            if area.extent.hi.y > self.extent.hi.y:
                self.extent.hi.y = area.extent.hi.y
            if not area.flags & 0x0001:
                self.nonCrouchAreas.append(area)
        self.nonCrouchAreasCount = len(self.nonCrouchAreas)
        self.hidingSpotsCount = len(self.hidingSpots)
        self.AllocateGrid()
        """
        FOR_EACH_LL( TheNavAreaList, it )
        {
            AddNavArea( TheNavAreaList[ it ] );
        }
        """
        self.hashTable = {}
        self.transientAreas = []
        for area in self.areas:
            self.AddNavArea(area)
        """
        //
        // Set up all the ladders
        //
        if (version >= 6)
        {
            result = filesystem->Read( &count, sizeof(unsigned int), file );
    
            // load the ladders
            for( i=0; i<count; ++i )
            {
                CNavLadder *ladder = new CNavLadder;
                ladder->Load( file, version );
                m_ladderList.AddToTail( ladder );
            }
        }
        else
        {
            BuildLadders();
        }
        """
        if self.version >= 6:
            self.laddercount = self.read('I')
            self.ladders = []
            for x in range(self.laddercount):
                self.ladders.append(NavLadder(self))
        else:
            fixme('Ladders are not supported for NAV Version below 6', 'NAV.__init__')
            self.BuildLadders()
        """
        // allow areas to connect to each other, etc
        FOR_EACH_LL( TheNavAreaList, pit )
        {
            CNavArea *area = TheNavAreaList[ pit ];
            area->PostLoad();
        }
        """
        for area in self.areas:
            area.PostLoad()
        """
        // allow hiding spots to compute information
        FOR_EACH_LL( TheHidingSpotList, hit )
        {
            HidingSpot *spot = TheHidingSpotList[ hit ];
            spot->PostLoad();
        }
        """
        for spot in self.hidingSpots:
            spot.PostLoad()
        """
        if ( version < 8 )
        {
            // Old nav meshes need to compute earliest occupy times
            FOR_EACH_LL( TheNavAreaList, nit )
            {
                CNavArea *area = TheNavAreaList[ nit ];
                area->ComputeEarliestOccupyTimes();
            }
        }
        """
        if self.version < 8:
            for area in self.areas:
                area.ComputeEarliestOccupyTimes()
        """
        ComputeBattlefrontAreas();
        """
        self.ComputeBattlefrontAreas()
        """
        // the Navigation Mesh has been successfully loaded
        m_isLoaded = true;
        """
        """
        filesystem->Close( file );
        """
        self.f.close()
        """
        WarnIfMeshNeedsAnalysis();
        """
        
    def AllocateGrid(self):
        """
        // add the areas to the grid
        AllocateGrid( extent.lo.x, extent.hi.x, extent.lo.y, extent.hi.y );
void CNavMesh::AllocateGrid( float minX, float maxX, float minY, float maxY )
{
    if (m_grid)
    {
        // destroy the grid
        if (m_grid)
            delete [] m_grid;

        m_grid = NULL;
    }

    m_minX = minX;
    m_minY = minY;

    m_gridSizeX = (int)((maxX - minX) / m_gridCellSize) + 1;
    m_gridSizeY = (int)((maxY - minY) / m_gridCellSize) + 1;

    m_grid = new NavAreaList[ m_gridSizeX * m_gridSizeY ];
}
        """
        self.minX = self.extent.lo.x
        self.minY = self.extent.lo.y
        self.gridSizeX = int(((self.extent.hi.x - self.minX) / self.gridCellSize) + 1)
        self.gridSizeY = int(((self.extent.hi.y - self.minY) / self.gridCellSize) + 1)
        # apparentely m_grid is a list of lists (in python) (thanks GODJonez)
        self.grid = map(lambda x: [],range(self.gridSizeX * self.gridSizeY))
        
    def AddNavArea(self, area):
        
        """
        if ( !m_grid )
        {
            // If we somehow have no grid (manually creating a nav area without loading or generating a mesh), don't crash
            AllocateGrid( 0, 0, 0, 0 );
        }
    
        // add to grid
        const Extent &extent = area->GetExtent();
    
        int loX = WorldToGridX( extent.lo.x );
        int loY = WorldToGridY( extent.lo.y );
        int hiX = WorldToGridX( extent.hi.x );
        int hiY = WorldToGridY( extent.hi.y );
        """
        loX = self.WorldToGridX(area.extent.lo.x)
        loY = self.WorldToGridY(area.extent.lo.y)
        hiX = self.WorldToGridX(area.extent.hi.x)
        hiY = self.WorldToGridY(area.extent.hi.y)
        """
        for( int y = loY; y <= hiY; ++y )
        {
            for( int x = loX; x <= hiX; ++x )
            {
                m_grid[ x + y*m_gridSizeX ].AddToTail( const_cast<CNavArea *>( area ) );
            }
        }
        """
        for y in range(loY, hiY + 1):
            for x in range(loX, hiX + 1):
                self.grid[x + y * self.gridSizeX].append(area)
        """
        // add to hash table
        int key = ComputeHashKey( area->GetID() );
        """
        key = self.ComputeHashKey(area.id)
        """
        if (m_hashTable[key])
        {
            // add to head of list in this slot
            area->m_prevHash = NULL;
            area->m_nextHash = m_hashTable[key];
            m_hashTable[key]->m_prevHash = area;
            m_hashTable[key] = area;
        }
        else
        {
            // first entry in this slot
            m_hashTable[key] = area;
            area->m_nextHash = NULL;
            area->m_prevHash = NULL;
        }
        """
        if key in self.hashTable:
            self.hashTable[key].insert(0, area)
        else:
            self.hashTable[key] = [area]
        """
        if ( area->GetAttributes() & NAV_MESH_TRANSIENT )
        {
            m_transientAreas.AddToTail( area );
        }
        """
        if area.flags & NavAttributeType['NAV_MESH_TRANSIENT']:
            self.transientAreas.append(area)
        """
        ++m_areaCount;
        """
        
    def BuildLadders(self):
        """
        // remove any left-over ladders
        DestroyLadders();
    
        trace_t result;
    
        CInfoLadder *entity = NULL;
        while( (entity = dynamic_cast< CInfoLadder * >(gEntList.FindEntityByClassname( entity, "info_ladder" ))) != NULL )
        {
            CreateLadder( entity->WorldAlignMins(), entity->WorldAlignMaxs(), NULL );
        }
        """
        todo('NAV.BuildLadders')
        
    def ComputeBattlefrontAreas(self):
        """
    #if 0
    #ifdef CSTRIKE_DLL
        ShortestPathCost cost;
        CBaseEntity *tSpawn, *ctSpawn;
    
        for( tSpawn = gEntList.FindEntityByClassname( NULL, "info_player_terrorist" );
             tSpawn;
             tSpawn = gEntList.FindEntityByClassname( tSpawn, "info_player_terrorist" ) )
        {
            CNavArea *tArea = TheNavMesh->GetNavArea( tSpawn->GetAbsOrigin() );
            if (tArea == NULL)
                continue;
    
            for( ctSpawn = gEntList.FindEntityByClassname( NULL, "info_player_counterterrorist" );
                 ctSpawn;
                 ctSpawn = gEntList.FindEntityByClassname( ctSpawn, "info_player_counterterrorist" ) )
            {
                CNavArea *ctArea = TheNavMesh->GetNavArea( ctSpawn->GetAbsOrigin() );
    
                if (ctArea == NULL)
                    continue;
    
                if (tArea == ctArea)
                {
                    m_isBattlefront = true;
                    return;
                }
    
                // build path between these two spawn points - assume if path fails, it at least got close
                // (ie: imagine spawn points that you jump down from - can't path to)
                CNavArea *goalArea = NULL;
                NavAreaBuildPath( tArea, ctArea, NULL, cost, &goalArea );
    
                if (goalArea == NULL)
                    continue;
    
    
    /**
     * @todo Need to enumerate ALL paths between all pairs of spawn points to find all battlefront areas
     */
    
                // find the area with the earliest overlapping occupy times
                CNavArea *battlefront = NULL;
                float earliestTime = 999999.9f;
    
                const float epsilon = 1.0f;
                CNavArea *area;
                for( area = goalArea; area; area = area->GetParent() )
                {
                    if (fabs(area->GetEarliestOccupyTime( TEAM_TERRORIST ) - area->GetEarliestOccupyTime( TEAM_CT )) < epsilon)
                    {
                    }
                    
                }
            }
        }
    #endif
    #endif
        """
        
    @staticmethod
    def ComputeHashKey(id):
        """
inline int CNavMesh::ComputeHashKey( unsigned int id ) const
{
    return id & 0xFF;
}
        """
        return id & 0xFF
    
    def WorldToGridX(self, wx):
        """
//--------------------------------------------------------------------------------------------------------------
inline int CNavMesh::WorldToGridX( float wx ) const
{ 
    int x = (int)( (wx - m_minX) / m_gridCellSize );

    if (x < 0)
        x = 0;
    else if (x >= m_gridSizeX)
        x = m_gridSizeX-1;
    
    return x;
}
        """
        x = int(self.minX / self.gridCellSize)
        if x < 0:
            return 0
        if x >= self.gridSizeX:
            return self.gridSizeX
        return x
    
    def WorldToGridY(self, wy):
        """
//--------------------------------------------------------------------------------------------------------------
inline int CNavMesh::WorldToGridY( float wy ) const
{ 
    int y = (int)( (wy - m_minY) / m_gridCellSize );

    if (y < 0)
        y = 0;
    else if (y >= m_gridSizeY)
        y = m_gridSizeY-1;
    
    return y;
}
        """
        y = int(self.minY / self.gridCellSize)
        if y < 0:
            return 0
        if y >= self.gridSizeY:
            return self.gridSizeY
        return y
        
    def getArea(self, position, noncrouch=False):
        if type(position) in (list, tuple):
            x, y, z = position
        else:
            x, y, z = position['x'], position['y'], position['z']
        if noncrouch:
            searchareas = self.nonCrouchAreas
        else:
            searchareas = self.areas
        for area in searchareas:
            if x > area.extent.hi.x:
                continue
            if x < area.extent.lo.x:
                continue
            if y > area.extent.hi.y:
                continue
            if y < area.extent.lo.y:
                continue
            if z > area.extent.hi.z:
                continue
            if z < area.extent.lo.z:
                continue
            return area
        return None
        
    def isWalkable(self, position):
        return bool(self.getArea(position, True))
    
    def isCoveredPosition(self, position):
        area = self.getArea(position)
        if not area:
            return False
        for hiding_spot in area.hidingspots:
            if hiding_spot.flags & HIDING_SPOT.IN_COVER:
                return True
        return False
    
    def isGoodSniperPosition(self, position):
        area = self.getArea(position)
        if not area:
            return False
        for hiding_spot in area.hidingspots:
            if hiding_spot.flags & HIDING_SPOT.GOOD_SNIPER_SPOT:
                return True
        return False
    
    def isIdealSniperPosition(self, position):
        area = self.getArea(position)
        if not area:
            return False
        for hiding_spot in area.hidingspots:
            if hiding_spot.flags & HIDING_SPOT.IDEAL_SNIPER_SPOT:
                return True
        return False
    
    def getRandomWalkablePosition(self):
        area = self.nonCrouchAreas[int(random.random() * self.nonCrouchAreasCount)]
        extent = area.extent
        x = extent.lo.x + (random.random() * (extent.hi.x - extent.lo.x))
        y = extent.lo.y + (random.random() * (extent.hi.y - extent.lo.y))
        z = extent.lo.z + (random.random() * (extent.hi.z - extent.lo.z))
        return (x,y,z)
    
    def getDict(self):
        d = {'filename': self.filename,
             'magic': self.magic,
             'version': self.version,
             'areacount': self.areacount,
             'extent': self.extent,
             'areas': map(lambda x: x.getDict(),self.areas),
             'spotEncounterList': self.spotEncounterList,
             'grid': self.grid}
        if self.version >= 4:
            d['bspsize'] = self.bspsize
        if self.version >= 5:
            d['places'] = self.places
        return d
    
    def __iter__(self):
        return iter(self.areas)
    
    def __str__(self):
        return str(self.getDict())
    
    def __repr__(self):
        return '<navlib.NAV: %s>' % self.filename
    
if __name__ == '__main__':
    from pprint import pprint
    import StringIO
    import sys
    s = StringIO.StringIO()
    sys.stderr = s
    nav = NAV('de_dust.nav')
    d = nav.getDict()
    d['_sys.stderr'] = s.getvalue().split('\n')
    f = open('de_dust.txt','wb')
    pprint(d, f)
    f.close()